home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / CUJ9102.ARJ / 9N02076A < prev    next >
Text File  |  1992-07-06  |  34KB  |  1,056 lines
  1.  
  2. /*
  3.  *    10-Oct-1990 - created
  4.  */
  5.  
  6. /******************************************************
  7.  *
  8.  *    Module:   olist.c
  9.  *
  10.  *    Purpose:  Functions to manage ordered lists using
  11.  *              skip lists.
  12.  *
  13.  *    (c) Copyright 1990 Kenneth L. Grogan, Jr.
  14.  *
  15.  *    You have permission to use this code for personal,
  16.  *    non-commercial purposes only. Any other use of this
  17.  *    code is prohibitted without the expressed written
  18.  *    consent of Kenneth L. Grogan, Jr.
  19.  *
  20.  ******************************************************/
  21.  
  22.                        /* don't include externals */
  23. #define OLIST_X
  24.  
  25. #include "local.h"
  26. #include "olist.h"
  27. #include "_olist.h"
  28.  
  29.                            /* random level factor p */
  30. #define P_FACTOR        0.25
  31. #define P_LEVEL         (P_FACTOR * RAND_MAX)
  32.                            /* 8 levels will accomodate */
  33.                            /* 65536 items per list */
  34.                            /* for P_FACTOR = .25 */
  35. #define MAX_LEVEL       8
  36.  
  37. #define this    ((SKIPLIST_T *)skip_list)
  38.  
  39. #define OLIST_IS_INVALID(sl)    ((sl) == NULL)
  40.                            /* get appropriate nil node */
  41. #define NIL(sl)         (nil_node[(sl)->key_type])
  42.  
  43.                            /* skip list node */
  44. struct sl_node
  45. {
  46.                            /* array of ptrs to nodes */
  47.     struct sl_node      **next;
  48.     SL_KEY              key;
  49.     void                *client_data;
  50. };
  51. typedef struct sl_node  SL_NODE;
  52.                            /* skip list level */
  53. typedef ubyte   SL_LEVEL;
  54.                            /* skip list */
  55. typedef struct
  56. {
  57.     SL_NODE     *header;
  58.     SL_NODE     *current;
  59.     size_t      size;
  60.     OLIST_KEY_T key_type;
  61.     SL_LEVEL    highest_level;
  62.     int         (*compare_func)();
  63. } SKIPLIST_T;
  64.                            /* maximum key values */
  65. static SL_KEY   max_key_value[OLIST_NUM_KEY_TYPES];
  66.                            /* nil pointers by key */
  67. static SL_NODE  *nil_node[OLIST_NUM_KEY_TYPES];
  68.  
  69.                            /* global error flag */
  70. int     olist_errno;
  71.  
  72.                            /* static prototypes */
  73. #include "__olist.h"
  74.  
  75. /*********************************************************
  76.  *  olist_new: 
  77.  *
  78.  *  Create a new skip list. The new list will contain no
  79.  *      nodes except the header node.
  80.  *
  81.  *  Returns a pointer to the new list, or NULL if an
  82.  *  error occurs.
  83.  *********************************************************/
  84.  
  85. OLIST olist_new (key_type, compare_func)
  86.     OLIST_KEY_T key_type;
  87.     int         (*compare_func)();
  88. {
  89.     register index_t    ii;
  90.     OLIST               skip_list;
  91.     SL_KEY              header_key;
  92.     SL_NODE             *header;
  93.  
  94.     static bool first_time = TRUE;
  95.  
  96.                            /* initialize */
  97.     if (first_time)
  98.     {
  99.         first_time = FALSE;
  100.         SET_MAXIMUM_KEY_VALUES();
  101.         if ( ! olist_make_nil_nodes())
  102.         {
  103.             olist_errno = OLIST_NO_MEMORY;
  104.             return (NULL);
  105.         }
  106.                          /* seed random generator */
  107.         RANDOMIZE();
  108.     }
  109.                            /* check key argument */
  110.     if ((key_type >= MIN_KEY) && (key_type <= MAX_KEY))
  111.     {
  112.                            /* make the list header node */
  113.         header = olist_make_node(MAX_LEVEL, header_key, NULL);
  114.         if (header != NULL)
  115.         {
  116.                            /* make the new skip list */
  117.             skip_list = (OLIST)malloc(sizeof(SKIPLIST_T));
  118.             if (skip_list != NULL)
  119.             {
  120.                 this->header = header;
  121.                 this->key_type = key_type;
  122.                 this->compare_func = compare_func;
  123.                            /* the list starts empty */
  124.                 olist_empty(skip_list);
  125.                            /* return the new skip list */
  126.                 olist_errno = OLIST_SUCCESS;
  127.                 return (skip_list);
  128.             }
  129.             else
  130.             {
  131.                 free(header);
  132.                 olist_errno = OLIST_NO_MEMORY;
  133.             }
  134.         }
  135.         else
  136.         {
  137.             olist_errno = OLIST_NO_MEMORY;
  138.         }
  139.     }
  140.     else
  141.     {
  142.                            /* invalid key type */
  143.         olist_errno = OLIST_INVALID_TYPE;
  144.     }
  145.     return (NULL);
  146. }
  147.  
  148. /***********************************************************
  149.  *  olist_kill:
  150.  *
  151.  *  Destroy the specified skip list by freeing all of its
  152.  *  associated memory.
  153.  *
  154.  *  Returns TRUE if successful, otherwise FALSE.
  155.  **********************************************************/
  156.  
  157. bool olist_kill (skip_list)
  158.     OLIST       skip_list;
  159. {
  160.  
  161.     olist_errno = OLIST_SUCCESS;
  162.                            /* check for valid skip list */
  163.     if (OLIST_IS_INVALID(this))
  164.     {
  165.         olist_errno = OLIST_INVALID;
  166.         return (FALSE);
  167.     }
  168.                            /* free each skip list nodes */
  169.     olist_free_all(skip_list);
  170.                            /* free the list header */
  171.     free(this->header->next);
  172.     free(this->header);
  173.                            /* prevent further access */
  174.     this->key_type = OLIST_NO_KEY;
  175.                            /* free the skip list */
  176.     free(this);
  177.                            /* skip list has been killed */
  178.     return (TRUE);
  179. }
  180.  
  181. /***********************************************************
  182.  *  olist_size:
  183.  *    Return the number of nodes in the specified skip list.
  184.  **********************************************************/
  185.  
  186. size_t olist_size (skip_list)
  187.     OLIST       skip_list;
  188. {
  189.  
  190.     olist_errno = OLIST_SUCCESS;
  191.                            /* check for valid skip list */
  192.     if (OLIST_IS_INVALID(this))
  193.     {
  194.         olist_errno = OLIST_INVALID;
  195.         return (NULL);
  196.     }
  197.                            /* return the list size */
  198.     return (this->size);
  199. }
  200.  
  201. /***********************************************************
  202.  *  olist_key_type:
  203.  *  Return the key type for the specified skip list.
  204.  **********************************************************/
  205.  
  206. OLIST_KEY_T olist_key_type (skip_list)
  207.     OLIST       skip_list;
  208. {
  209.  
  210.     olist_errno = OLIST_SUCCESS;
  211.                            /* check for valid skip list */
  212.     if (OLIST_IS_INVALID(this))
  213.     {
  214.         olist_errno = OLIST_INVALID;
  215.         return (OLIST_NO_KEY);
  216.     }
  217.                            /* return the list key type */
  218.     return (this->key_type);
  219. }
  220.  
  221. /***********************************************************
  222.  *  olist_add:
  223.  *
  224.  *  Add the specified client data to the specified skip list.
  225.  *  The argument replace_data has the following effect:
  226.  *
  227.  *  value  |   key already in the list   |  key not in the list
  228.  *  -----------------------------------------------------------
  229.  *  TRUE   | replace client data for key |  add key to the list
  230.  *  FALSE  |   return KEY_EXISTS error   |  add key to the list
  231.  *
  232.  *  Returns TRUE if the data was inserted or replaced,
  233.  *  otherwise FALSE.
  234.  **********************************************************/
  235.  
  236. bool olist_add (skip_list, key_type, inkey, client_data,
  237.                                replace_data)
  238.     OLIST       skip_list;
  239.     OLIST_KEY_T key_type;
  240.     void        *inkey;
  241.     void        *client_data;
  242.     bool        replace_data;
  243. {
  244.     register index_t    ii;
  245.     SL_LEVEL            new_level;
  246.     SL_KEY              search_key;
  247.     SL_NODE             *new_node;
  248.     SL_NODE             *update_node[MAX_LEVEL];
  249.  
  250.  
  251.     olist_errno = OLIST_SUCCESS;
  252.                            /* check for valid skip list */
  253.     if (OLIST_IS_INVALID(this) ||
  254.         (KEY_IS_INVALID(this, key_type, inkey)))
  255.     {
  256.         olist_errno = OLIST_INVALID;
  257.         return (FALSE);
  258.     }
  259.                            /* get the appropriate key */
  260.     GET_KEY(search_key, key_type, inkey);
  261.                            /* start with the highest */
  262.                            /* level in the header node */
  263.     new_node = this->header;
  264.     ii = this->highest_level + 1;
  265.     do {
  266.         --ii;
  267.                            /* get key before search key */
  268.         while (KEY_LT(this, new_node->next[ii]->key, search_key))
  269.         {
  270.             new_node = new_node->next[ii];
  271.         }
  272.         update_node[ii] = new_node;
  273.     } while (ii > 0);
  274.                            /* advance to the expected */
  275.                            /* search key location */
  276.     new_node = new_node->next[0];
  277.                            /* key equals search key? */
  278.     if (KEY_EQ(this, new_node->key, search_key))
  279.     {
  280.                            /* key already exists */
  281.         if (replace_data)
  282.         {
  283.                            /* just replace the data */
  284.             new_node->client_data = client_data;
  285.         }
  286.         else
  287.         {
  288.             olist_errno = OLIST_KEY_EXISTS;
  289.             return (FALSE);
  290.         }
  291.     }
  292.     else
  293.     {
  294.                            /* get a random level */
  295.         new_level = olist_get_new_level();
  296.         if (new_level > this->highest_level)
  297.         {
  298.                            /* max level increase is 1 */
  299.             new_level = this->highest_level + 1;
  300.             update_node[new_level] = this->header;
  301.         }
  302.                            /* make the new node */
  303.         new_node = olist_make_node(new_level + 1, search_key,
  304.                                              client_data);
  305.         if (new_node == NULL)
  306.         {
  307.             olist_errno = OLIST_NO_MEMORY;
  308.             return (FALSE);
  309.         }
  310.                            /* update highest level */
  311.         if (new_level > this->highest_level)
  312.         {
  313.             this->highest_level = new_level;
  314.         }
  315.                            /* update the node pointers */
  316.         for (ii = 0; ii <= new_level; ++ii)
  317.         {
  318.             new_node->next[ii] = update_node[ii]->next[ii];
  319.             update_node[ii]->next[ii] = new_node;
  320.         }
  321.                            /* inserted one new node */
  322.         ++(this->size);
  323.     }
  324.     return (TRUE);
  325. }
  326.  
  327. /***********************************************************
  328.  *    olist_remove
  329.  *
  330.  *    Remove the specified node from the specified skip list.
  331.  *    Returns TRUE if the data was removed, otherwise FALSE.
  332.  **********************************************************/
  333.  
  334. bool olist_remove (skip_list, key_type, inkey)
  335.     OLIST       skip_list;
  336.     OLIST_KEY_T key_type;
  337.     void        *inkey;
  338. {
  339.     register index_t    ii;
  340.     SL_KEY              search_key;
  341.     SL_NODE             *target_node;
  342.     SL_NODE             *update_node[MAX_LEVEL];
  343.  
  344.  
  345.     olist_errno = OLIST_SUCCESS;
  346.                            /* check for valid skip list */
  347.     if (OLIST_IS_INVALID(this) ||
  348.         (KEY_IS_INVALID(this, key_type, inkey)))
  349.     {
  350.         olist_errno = OLIST_INVALID;
  351.         return (FALSE);
  352.     }
  353.                            /* get the appropriate key */
  354.     GET_KEY(search_key, key_type, inkey);
  355.                            /* start with the highest */
  356.                            /* level in the header node */
  357.     target_node = this->header;
  358.     ii = this->highest_level + 1;
  359.     do {
  360.         --ii;
  361.                            /* get key before search key */
  362.         while (KEY_LT(this, target_node->next[ii]->key,
  363.                                       search_key))
  364.         {
  365.             target_node = target_node->next[ii];
  366.         }
  367.         update_node[ii] = target_node;
  368.     } while (ii > 0);
  369.                            /* advance to the expected */
  370.                            /* search key location */
  371.     target_node = target_node->next[0];
  372.     if (KEY_EQ(this, target_node->key, search_key))
  373.     {
  374.                            /* for each level, replace */
  375.                            /* pointers to the target */
  376.                            /* node with the pointers */
  377.                            /* in the target node */
  378.         for (ii = 0; ii <= this->highest_level; ++ii)
  379.         {
  380.             if (update_node[ii]->next[ii] != target_node) break;
  381.             update_node[ii]->next[ii] = target_node->next[ii];
  382.         }
  383.         if (target_node == this->current)
  384.         {
  385.                            /* removing the current node */
  386.             this->current = target_node->next[0];
  387.         }
  388.         free(target_node);
  389.                            /* if the target node is */
  390.                            /* the only highest level */
  391.                            /* node, then decrease the */
  392.                            /* highest level */
  393.         while ((this->highest_level > 0) &&
  394.                (this->header->next[this->highest_level] ==
  395.                                                      NIL(this)))
  396.         {
  397.             --(this->highest_level);
  398.         }
  399.                            /* decrease the list size */
  400.         --(this->size);
  401.     }
  402.     else
  403.     {
  404.         olist_errno = OLIST_NOT_FOUND;
  405.         return (FALSE);
  406.     }
  407.  
  408.     return (TRUE);
  409. }
  410.  
  411. /***********************************************************
  412.  *                       olist_remove_all
  413.  *
  414.  * Remove all the nodes in the specified skip list.
  415.  * Returns TRUE if all data has been removed, otherwise FALSE.
  416.  **********************************************************/
  417.  
  418. bool olist_remove_all (skip_list)
  419.     OLIST       skip_list;
  420. {
  421.  
  422.     olist_errno = OLIST_SUCCESS;
  423.                            /* check for valid skip list */
  424.     if (OLIST_IS_INVALID(this))
  425.     {
  426.         olist_errno = OLIST_INVALID;
  427.         return (FALSE);
  428.     }
  429.                            /* free each skip list node */
  430.     olist_free_all(skip_list);
  431.                            /* skip list is now empty */
  432.     return (TRUE);
  433. }
  434.  
  435. /***********************************************************
  436.  *
  437.  *                              olist_find
  438.  *
  439.  *  Search the specified skip list for the node with the
  440.  *  specified key. If found, make this node the current node.
  441.  *
  442.  *  Returns the pointer to the client data in the found node,
  443.  *  or NULL if the key is not found or an error occurs.
  444.  *
  445.  **********************************************************/
  446.  
  447. void *olist_find (skip_list, key_type, inkey)
  448.     OLIST       skip_list;
  449.     OLIST_KEY_T key_type;
  450.     void        *inkey;
  451. {
  452.     register index_t    ii;
  453.     SL_KEY              search_key;
  454.     SL_NODE             *target_node;
  455.  
  456.  
  457.     olist_errno = OLIST_SUCCESS;
  458.                            /* check for valid skip list */
  459.     if (OLIST_IS_INVALID(this) ||
  460.         (KEY_IS_INVALID(this, key_type, inkey)))
  461.     {
  462.         olist_errno = OLIST_INVALID;
  463.         return (NULL);
  464.     }
  465.                            /* get the appropriate key */
  466.     GET_KEY(search_key, key_type, inkey);
  467.                            /* start with the highest */
  468.                            /* level in the header node */
  469.     target_node = this->header;
  470.     ii = this->highest_level + 1;
  471.     do {
  472.         --ii;
  473.                            /* get key before search key */
  474.         while (KEY_LT(this, target_node->next[ii]->key,
  475.                                   search_key))
  476.         {
  477.             target_node = target_node->next[ii];
  478.         }
  479.     } while (ii > 0);
  480.                            /* advance to the expected */
  481.                            /* search key location */
  482.     target_node = target_node->next[0];
  483.     if (KEY_EQ(this, target_node->key, search_key))
  484.     {
  485.                            /* found the search key */
  486.         this->current = target_node;
  487.                            /* return the client data */
  488.         return (target_node->client_data);
  489.     }
  490.                            /* search key is not in list */
  491.     olist_errno = OLIST_NOT_FOUND;
  492.     return (NULL);
  493. }
  494.  
  495. /***********************************************************
  496.  *
  497.  *                              olist_query
  498.  *  Search the specified skip list for the node with the
  499.  *  specified key. If found, make this node the current
  500.  *  node. If not found, then find the node with the next
  501.  *  closest key and make that node current.  If
  502.  *  find_before is TRUE, find the closest node before,
  503.  *  otherwise find the closest node after. Set the value
  504.  *  pointed to by the appropriate key type pointer to the
  505.  *  key value of the found node.
  506.  * 
  507.  *  Returns the pointer to the client data in the found
  508.  *  node, or NULL if there is no node found before or
  509.  *  after, or an error occurs.
  510.  *
  511.  **********************************************************/
  512.  
  513. void *olist_query (skip_list, key_type, inkey, outkey,
  514.                               find_before)
  515.     OLIST       skip_list;
  516.     OLIST_KEY_T key_type;
  517.     void        *inkey;
  518.     void        *outkey;
  519.     bool        find_before;
  520. {
  521.     register index_t    ii;
  522.     SL_KEY              search_key;
  523.     SL_NODE             *node_before;
  524.     SL_NODE             *target_node;
  525.  
  526.  
  527.     olist_errno = OLIST_SUCCESS;
  528.                            /* check for valid skip list */
  529.     if (OLIST_IS_INVALID(this) ||
  530.         (KEY_IS_INVALID(this, key_type, inkey)))
  531.     {
  532.         olist_errno = OLIST_INVALID;
  533.         return (NULL);
  534.     }
  535.                            /* get the appropriate key */
  536.     GET_KEY(search_key, key_type, inkey);
  537.                            /* start with the highest */
  538.                            /* level in the header node */
  539.     node_before = this->header;
  540.     ii = this->highest_level + 1;
  541.     do {
  542.         --ii;
  543.                            /* get key before search key */
  544.         while (KEY_LT(this, node_before->next[ii]->key,
  545.                               search_key))
  546.         {
  547.             node_before = node_before->next[ii];
  548.         }
  549.     } while (ii > 0);
  550.                            /* advance to the expected */
  551.                            /* search key location */
  552.     target_node = node_before->next[0];
  553.     if ( ! KEY_EQ(this, target_node->key, search_key))
  554.     {
  555.         if (find_before)
  556.         {
  557.                            /* use the preceding node */
  558.             target_node = node_before;
  559.         }
  560.         if ((target_node == this->header) || (target_node ==
  561.                                    NIL(this)))
  562.         {
  563.                            /* no node before or after */
  564.             olist_errno = OLIST_NOT_FOUND;
  565.             return (NULL);
  566.         }
  567.     }
  568.                            /* make found node current */
  569.     this->current = target_node;
  570.                            /* set the appropriate key */
  571.     SET_KEY(target_node->key, key_type, outkey);
  572.                            /* return the client data */
  573.     return (target_node->client_data);
  574. }
  575.  
  576. /***********************************************************
  577.  *
  578.  *                              olist_get_last
  579.  *
  580.  *  Get the client data for the last node in the specified
  581.  *  skip list (this would normally be the node with the largest
  582.  *  key in the list). Set the value pointed to by the
  583.  *  appropriate key type pointer to the key value of the last
  584.  *  node. Does not affect the current node.
  585.  *
  586.  *  Returns the pointer to the client data of the last node
  587.  *  in the list, or NULL if the list is empty or an error occurs.
  588.  *
  589.  **********************************************************/
  590.  
  591. void *olist_get_last (skip_list, key_type, outkey)
  592.     OLIST       skip_list;
  593.     OLIST_KEY_T key_type;
  594.     void        *outkey;
  595. {
  596.     register index_t    ii;
  597.     SL_NODE             *target_node;
  598.  
  599.  
  600.     olist_errno = OLIST_SUCCESS;
  601.                            /* check for valid skip list */
  602.     if (OLIST_IS_INVALID(this) || (key_type != this->key_type))
  603.     {
  604.         olist_errno = OLIST_INVALID;
  605.         return (NULL);
  606.     }
  607.                            /* start with the highest */
  608.                            /* level in the header node */
  609.     target_node = this->header;
  610.     if (target_node->next[0] == NIL(this))
  611.     {
  612.         olist_errno = OLIST_EMPTY;
  613.         return (NULL);
  614.     }
  615.     ii = this->highest_level + 1;
  616.     do {
  617.         --ii;
  618.                            /* skip across node levels */
  619.         while (target_node->next[ii] != NIL(this))
  620.         {
  621.             target_node = target_node->next[ii];
  622.         }
  623.     } while (ii > 0);
  624.                            /* set the appropriate key */
  625.     SET_KEY(target_node->key, key_type, outkey);
  626.                            /* return the client data */
  627.     return (target_node->client_data);
  628. }
  629.  
  630. /***********************************************************
  631.  *
  632.  *                              olist_do_first
  633.  *
  634.  *  Get the client data for the first node in the specified
  635.  *  skip list (this would normally be the node with the
  636.  *  smallest key in the list) and make this node the current
  637.  *  node if set_current is TRUE. Set the value pointed to by
  638.  *  the appropriate key type pointer to the key value of the
  639.  *  first node.
  640.  *
  641.  *  Returns the pointer to the client data of the first node
  642.  *  in the list, or NULL if the list is empty or an error occurs.
  643.  *
  644.  **********************************************************/
  645.  
  646. void *olist_do_first (skip_list, key_type, outkey, set_current)
  647.     OLIST       skip_list;
  648.     OLIST_KEY_T key_type;
  649.     void        *outkey;
  650.     bool        set_current;
  651. {
  652.     SL_NODE     *target_node;
  653.  
  654.  
  655.     olist_errno = OLIST_SUCCESS;
  656.                            /* check for valid skip list */
  657.     if (OLIST_IS_INVALID(this) || (key_type != this->key_type))
  658.     {
  659.         olist_errno = OLIST_INVALID;
  660.         return (NULL);
  661.     }
  662.                            /* the lowest header level */
  663.                            /* points to the first node */
  664.     target_node = this->header->next[0];
  665.     if (target_node == NIL(this))
  666.     {
  667.         olist_errno = OLIST_EMPTY;
  668.         return (NULL);
  669.     }
  670.     if (set_current)
  671.     {
  672.                            /* make this node current */
  673.         this->current = target_node;
  674.     }
  675.                            /* set the appropriate key */
  676.     SET_KEY(target_node->key, key_type, outkey);
  677.                            /* return the client data */
  678.     return (target_node->client_data);
  679. }
  680.  
  681. /***********************************************************
  682.  *
  683.  *                              olist_do_next
  684.  *
  685.  *  Get the client data for the node following the current
  686.  *  node in the specified skip list (this will be the next
  687.  *  node in the key sequence) and make this node the current
  688.  *  node if set_current is TRUE. Set the value pointed to by
  689.  *  the appropriate key type pointer to the key value of the
  690.  *  next node.
  691.  *
  692.  *  Returns the pointer to the client data of the next node
  693.  *  in the list, or NULL if there is no current node, the 
  694.  *  list is empty or an error occurs.
  695.  *
  696.  **********************************************************/
  697.  
  698. void *olist_do_next (skip_list, key_type, outkey, set_current)
  699.     OLIST       skip_list;
  700.     OLIST_KEY_T key_type;
  701.     void        *outkey;
  702.     bool        set_current;
  703. {
  704.     SL_NODE     *target_node;
  705.  
  706.  
  707.     olist_errno = OLIST_SUCCESS;
  708.                            /* check for valid skip list */
  709.     if (OLIST_IS_INVALID(this) || (key_type != this->key_type))
  710.     {
  711.         olist_errno = OLIST_INVALID;
  712.         return (NULL);
  713.     }
  714.                            /* check for current node */
  715.     if (this->current == NULL)
  716.     {
  717.         olist_errno = OLIST_NO_CURRENT;
  718.         return (NULL);
  719.     }
  720.                            /* the lowest node level */
  721.                            /* points to the next node */
  722.     target_node = this->current->next[0];
  723.     if (target_node == NIL(this))
  724.     {
  725.                            /* at end of the list */
  726.         olist_errno = OLIST_END_OF_LIST;
  727.         return (NULL);
  728.     }
  729.     if (set_current)
  730.     {
  731.                            /* make this node current */
  732.         this->current = target_node;
  733.     }
  734.                            /* set the appropriate key */
  735.     SET_KEY(target_node->key, key_type, outkey);
  736.                            /* return the client data */
  737.     return (target_node->client_data);
  738. }
  739.  
  740. /***********************************************************
  741.  *
  742.  *                           olist_get_current
  743.  *
  744.  *  Get the client data for the current node in the specified
  745.  *  skip list. Set the value pointed to by the appropriate
  746.  *  key type pointer to the key value of the next node. Does
  747.  *  not affect the current node.
  748.  *
  749.  *  Returns the pointer to the client data of the current node
  750.  *  in the list, or NULL if there is no current node or an
  751.  *  error occurs.
  752.  *
  753.  **********************************************************/
  754.  
  755. void *olist_get_current (skip_list, key_type, outkey)
  756.     OLIST       skip_list;
  757.     OLIST_KEY_T key_type;
  758.     void        *outkey;
  759. {
  760.     olist_errno = OLIST_SUCCESS;
  761.                            /* check for valid skip list */
  762.     if (OLIST_IS_INVALID(this) || (key_type != this->key_type))
  763.     {
  764.         olist_errno = OLIST_INVALID;
  765.         return (NULL);
  766.     }
  767.                            /* check for current node */
  768.     if (this->current == NULL)
  769.     {
  770.         olist_errno = OLIST_NO_CURRENT;
  771.         return (NULL);
  772.     }
  773.     if (this->current == NIL(this))
  774.     {
  775.                            /* at end of the list */
  776.         olist_errno = OLIST_END_OF_LIST;
  777.         return (NULL);
  778.     }
  779.                            /* set the appropriate key */
  780.     SET_KEY(this->current->key, key_type, outkey);
  781.                            /* return the client data */
  782.     return (this->current->client_data);
  783. }
  784.  
  785. /***********************************************************
  786.  *
  787.  *                              olist_compares
  788.  *
  789.  *  Returns the number of compares required to find the node
  790.  *  with the specified key in the specified skip list, or
  791.  *  zero (0) if the key is not found or an error occurs.
  792.  *
  793.  **********************************************************/
  794.  
  795. int olist_compares (skip_list, key_type, inkey)
  796.     OLIST       skip_list;
  797.     OLIST_KEY_T key_type;
  798.     void        *inkey;
  799. {
  800.     register index_t    ii;
  801.     SL_KEY              search_key;
  802.     SL_NODE             *target_node;
  803.     int                 num_compares = 0;
  804.  
  805.  
  806.     olist_errno = OLIST_SUCCESS;
  807.                            /* check for valid skip list */
  808.     if (OLIST_IS_INVALID(this) ||
  809.         (KEY_IS_INVALID(this, key_type, inkey)))
  810.     {
  811.         olist_errno = OLIST_INVALID;
  812.         return (0);
  813.     }
  814.                            /* get the appropriate key */
  815.     GET_KEY(search_key, key_type, inkey);
  816.                            /* start with the highest */
  817.                            /* level in the header node */
  818.     target_node = this->header;
  819.     ii = this->highest_level + 1;
  820.     do {
  821.         --ii;
  822.                            /* get key before search key */
  823.         while (KEY_LT(this, target_node->next[ii]->key,
  824.                    search_key))
  825.         {
  826.             target_node = target_node->next[ii];
  827.             ++num_compares;
  828.         }
  829.         ++num_compares;
  830.     } while (ii > 0);
  831.                            /* advance to the expected */
  832.                            /* search key location */
  833.     target_node = target_node->next[0];
  834.     ++num_compares;
  835.     if (KEY_EQ(this, target_node->key, search_key))
  836.     {
  837.                            /* return the client data */
  838.         return (num_compares);
  839.     }
  840.                            /* search key is not in list */
  841.     olist_errno = OLIST_NOT_FOUND;
  842.     return (0);
  843. }
  844.  
  845. /***********************************************************
  846.  *
  847.  *                              olist_report
  848.  *
  849.  *  Print to stdout the number of nodes at each level of the
  850.  *  specified skip list.
  851.  *
  852.  *  Returns the TRUE if successful, otherwise FALSE.
  853.  *
  854.  **********************************************************/
  855.  
  856. bool olist_report (skip_list)
  857.     OLIST       skip_list;
  858. {
  859.     register index_t    ii;
  860.     SL_NODE             *target_node;
  861.     size_t              node_count;
  862.     size_t              total_node_count = 0;
  863.  
  864.  
  865.     olist_errno = OLIST_SUCCESS;
  866.                            /* check for valid skip list */
  867.     if (OLIST_IS_INVALID(this))
  868.     {
  869.         olist_errno = OLIST_INVALID;
  870.         return (FALSE);
  871.     }
  872.                            /* start with the highest */
  873.                            /* level in the header node */
  874.     ii = this->highest_level + 1;
  875.     if (this->size > 0) do
  876.     {
  877.         --ii;
  878.         node_count = 0;
  879.         target_node = this->header;
  880.                            /* skip across node levels */
  881.         while (target_node->next[ii] != NIL(this))
  882.         {
  883.             target_node = target_node->next[ii];
  884.             ++node_count;
  885.         }
  886.                            /* remove higher level */
  887.                            /* counts from this level */
  888.         node_count = node_count - total_node_count;
  889.         total_node_count = total_node_count + node_count;
  890.         printf("\nskip list level %u : %5u nodes (%d%%)",
  891.                ii + 1, node_count,
  892.                (int)(100.0 * ((double)node_count /
  893.                                         (double)this->size)));
  894.     } while (ii > 0);
  895.     if (total_node_count == this->size)
  896.     {
  897.         printf("\n\n Total number of nodes = %d\n",
  898.                                 total_node_count);
  899.     }
  900.     else
  901.     {
  902.         printf("\n\n *** Total number of nodes does not \
  903. match list size\n");
  904.     }
  905.     return (TRUE);
  906. }
  907.  
  908. /***********************************************************
  909.  *
  910.  *                           olist_free_all
  911.  *
  912.  *          Free all of the nodes in the specified skip list.
  913.  *
  914.  **********************************************************/
  915.  
  916. static void olist_free_all (skip_list)
  917.     OLIST       skip_list;
  918. {
  919.     SL_NODE     *next_node;
  920.     SL_NODE     *target_node;
  921.  
  922.                            /* free each skip list node */
  923.     next_node = this->header->next[0];
  924.     while (next_node != NIL(this))
  925.     {
  926.         target_node = next_node;
  927.         next_node = target_node->next[0];
  928.         free(target_node);
  929.     }
  930.                            /* initialize as empty list */
  931.     olist_empty(skip_list);
  932. }
  933.  
  934. /***********************************************************
  935.  *
  936.  *                              olist_empty
  937.  *
  938.  *          Initialize the specified skip list as an empty list.
  939.  *
  940.  **********************************************************/
  941.  
  942. static void olist_empty (skip_list)
  943.     OLIST       skip_list;
  944. {
  945.     register index_t    ii;
  946.  
  947.  
  948.     for (ii = 0; ii < MAX_LEVEL; ++ii)
  949.     {
  950.         this->header->next[ii] = NIL(this);
  951.     }
  952.     this->size = 0;
  953.     this->highest_level = 0;
  954.     this->current = NULL;
  955. }
  956.  
  957. /***********************************************************
  958.  *
  959.  *                          olist_make_nil_nodes
  960.  *
  961.  *  Make the nil node for each key type and initialize the
  962.  *  keys and levels.
  963.  *
  964.  *  Return TRUE if successful, otherwise FALSE.
  965.  *
  966.  **********************************************************/
  967.  
  968. static bool olist_make_nil_nodes ()
  969. {
  970.     register index_t    ii, jj;
  971.                            /* the key for each nil */
  972.                            /* must be the larger than */
  973.                            /* the largest available key */
  974.     for (ii = MIN_KEY; ii <= MAX_KEY; ++ii)
  975.     {
  976.         nil_node[ii] = olist_make_node(MAX_LEVEL,
  977.                                      max_key_value[ii], NULL);
  978.         if (nil_node[ii] == NULL)
  979.         {
  980.                            /* out of memory, so free */
  981.                            /* the nodes already made */
  982.             for (jj = MIN_KEY; jj < ii; ++jj)
  983.             {
  984.                 free(nil_node[jj]);
  985.             }
  986.             return (FALSE);
  987.         }
  988.     }
  989.     for (ii = MIN_KEY; ii <= MAX_KEY; ++ii)
  990.     {
  991.         for (jj = 0; jj < MAX_LEVEL; ++jj)
  992.         {
  993.                            /* next node points to nil */
  994.             nil_node[ii]->next[jj] = nil_node[ii];
  995.         }
  996.     }
  997.     return (TRUE);
  998. }
  999.  
  1000. /***********************************************************
  1001.  *                   olist_get_new_level
  1002.  *
  1003.  *      Return a random level from zero to MAX_LEVEL - 1.
  1004.  **********************************************************/
  1005.     
  1006. static SL_LEVEL olist_get_new_level ()
  1007. {
  1008.     SL_LEVEL    new_level = 0;
  1009.  
  1010.                            /* generate a random level */
  1011.     while (RANDOM() < P_LEVEL)
  1012.     {
  1013.         ++new_level;
  1014.     }
  1015.     return ((SL_LEVEL)(MIN(new_level, MAX_LEVEL - 1)));
  1016. }
  1017.  
  1018. /***********************************************************
  1019.  *                    olist_make_node
  1020.  *  Create a new node structure and fill it with the
  1021.  *  specified values.
  1022.  *
  1023.  *  Return a pointer to the new node, or NULL if an error
  1024.  *  has occurs.
  1025.  **********************************************************/
  1026.     
  1027. static SL_NODE *olist_make_node (level_num, new_key,
  1028.                           client_data)
  1029.     SL_LEVEL    level_num;
  1030.     SL_KEY      new_key;
  1031.     void        *client_data;
  1032. {
  1033.     SL_NODE     *new_node;
  1034.     SL_NODE     **new_node_next;
  1035.  
  1036.                            /* make the new node */
  1037.     new_node = (SL_NODE *)malloc(sizeof(SL_NODE));
  1038.     if (new_node != NULL)
  1039.     {
  1040.                            /* make the next node array */
  1041.         new_node_next = (SL_NODE **)malloc(level_num *
  1042.                                                sizeof(SL_NODE *));
  1043.         if (new_node_next != NULL)
  1044.         {
  1045.             new_node->next = new_node_next;
  1046.             new_node->key = new_key;
  1047.             new_node->client_data = client_data;
  1048.                            /* return the new node */
  1049.             return (new_node);
  1050.         }
  1051.         free(new_node);
  1052.     }
  1053.     return (NULL);
  1054. }
  1055.  
  1056.